/* 
 * Climbing Stairs
 * f(n) = f(n-1) + f(n-2)
 */

#include "../../func.h"

int climbStairs(int n)
{
    int prev = 0;
    int cur = 1;
    for (int i = 1; i <= n; ++i)
    {
        int tmp = cur;
        cur += prev;
        prev = tmp;
    }
    return cur;
}

int climbStairs1(int n)
{
    const double s = sqrt(5);
    return floor((pow((1 + s) / 2, n + 1) + pow((1 - s) / 2, n + 1)) / s + 0.5);
}